/*
* 二叉堆：
*   二叉堆是一种特殊的二叉树，有以下两个特性。
*   它是一棵完全二叉树，表示树的每一层都有左侧和右侧子节点（除了最后一层的叶节点），并且最后一层的叶节点尽可能都是左侧子节点，这叫做结构特性。
*   二叉堆不是最小堆就是最大堆。最小堆可以快速导出树的最小值，最大堆可以快速导出树的最大值。
*   所有的节点都大于等于最小堆的最小值或小于等于最大堆的最大值。这叫做堆特性。
*
* */
class MinHeap{ //因为二叉堆是完全按顺序来排列的，没有任何特殊结构，所以用类似数组的结构来表示就行，因为数组下标就是递增顺序的
    constructor() {
        this.heap = []
    }
    getLeftIndex(index){ //指定节点的索引
        //某个节点的左侧子节点索引
        return 2 * index + 1
    }

    getRightIndex(index){
        return 2 * index + 2
    }

    getParentIndex(index){
        if(index === 0){ //如果是根节点，那么它没有父节点
            return undefined
        }
        //剩下的就是非根节点的情况 减1减2都行，减1向下取整，减2向上取整
        return Math.floor((index-1)/2) //左侧子节点的父节点是（i-1）/2，右侧子节点的父节点是（i-2）/2，所以减1用向下取整
    }

    insert(value){
        if(value){
            this.heap.push(value) //把值添加到数组最后面
            //提档，把数组中最小值提到最上面
            this.shiftUp(this.heap.length-1) //从最后一个值开始一个个提档
            return true
        }
        //如果没有值返回false
        return false
    }

    shiftUp(index){ //提档
        let parentIndex = this.getParentIndex(index) //获取父节点索引
        while(index > 0 && this.heap[parentIndex] > this.heap[index]){ //一直往上交换，直到换到顶
            this.swap(this.heap,parentIndex,index)
            index = parentIndex
            parentIndex = this.getParentIndex(index)
        }
    }

    swap(arr,a,b){ //交换
        let temp = arr[a]
        arr[a] = arr[b]
        arr[b] = temp
    }

    size(){
        return this.heap.length
    }

    isEmpty(){
        return this.heap.length === 0 //方法一
        //return this.size() === 0 //方法二
    }

    findMinValue(){
        return this.isEmpty()?undefined:this.heap[0]
    }

    extract(){ //删除顶上最小值
        if(this.isEmpty()){ //如果为空
            return undefined
        }
        if(this.size() === 1){
            return this.heap.shift()
        }
        let removeNode = this.heap[0] //把当前最小的返回回去
        this.heap[0] = this.heap.pop() //把最大一个挪到最前面
        this.shiftDown(0) //最大的往下挪
        return removeNode
    }

    shiftDown(index){ //一次次把最大值往下挪
        let currentIndex = index
        let leftIndex = this.getLeftIndex(index) //获取左侧子节点
        let rightIndex = this.getRightIndex(index) //获取右侧子节点
        let size = this.size() //当索引超出长度的时候
        if(leftIndex < size && this.heap[currentIndex] > this.heap[leftIndex]){
            currentIndex = leftIndex
        }
        if(rightIndex < size && this.heap[currentIndex] > this.heap[rightIndex]){
            currentIndex = rightIndex
        }
        if(currentIndex !== index){
            this.swap(this.heap,currentIndex,index)
            this.shiftDown(currentIndex)
        }
    }
}